The present invention relates to an apparatus for finding a quotient, especially to an apparatus for finding a quotient in a digital system.
Inherently, division operation is a sequential operation. The quotient digits are produced only after the sign of the remainder has been detected. As a result, division operation is much slower than a multiplication operation. Efforts have been put in speeding up the division operation. It is noted that the SRT algorithm (C. V. Freiman, "Statistical Analysis of Certain Binary division algorithms," Proc. IRE, Vol. 49, Jan. 1961, pp. 91-103; K. Hwang, Computer Arithmetic: Principles, Architectures, and Design, 1979, pp. 222-223) eliminates the restoring operations of the partial remainders. Another algorithm disclosed by K. Hwang confines the quotient digits either to be 1 or -1, depending on the signs of remainders. However, the bottleneck of those algorithms lies in sign detection of the remainder. Fast addition algorithms such as CLA (carry-lookahead addition) shorten the operation time, but results in complex hardware structures.
Recently, division algorithms based on SD (signed-digit) number representation was proposed which is much faster than the previous algorithm (S. Kuninobu et al., "Design of High Speed MOS Multiplier and Divider Using Redundant Binary Representation," IEEE Proceeding of Symposium on Computer Arithmetic, 1987, pp. 80-86). This algorithm considerably shortens the time for remainder subtraction by using carry-propagation-free SD addition. However, it is much more complex because in each iteration the SD algorithm must check three most significant digit (MSD) bits of the remainder to decide the quotient digit in the set of {-1, 0, 1}, and then perform the SD addition. Moreover, the final SD result must be converted to binary representation. Also note that the signed-digit addition is more complicated than the conventional carry-save adder (CSA).
Another type of algorithm entirely avoids the slow subtract-detect-shift type of operation previously mentioned. They transform the division operation to a series of multiplication operations that converge to the original quotient. Among the examples are the constant convergence (S. Waser and M. J. Flynn, Introduction to Arithmetic for Digital Systems Designers, New York: CBS College Publishing, Chap. 5, 1982) and quadratic convergence (P. Markenstein, "Computation of Elementary Functions on the IBM RISC System/6000 Processor," IBM Journal of Research and Development, Vol. 34, 1990, pp. 111-119; D. A. Patterson and J. L. Hennessy, Computer: A Quantitative Approach, San Mateo, Calif., Morgan Kaufman, 1990) division algorithms which are based on Newton-Raphson algorithm. They are often found in multiplier-based processors. They are still sequential type of operation to certain degree, and obviously require much more shift-and-add operations.
There is an on-line division algorithm that facilitates serial/serial division operation (K. S. Trivedi and M. D. Ercegovac, "On-Line Algorithms for Division and Multiplication," IEEE Trans. on Computers, Vol. C-26, No. 7, July 1977). This algorithm has advantages such as that: (a) it is pipelined at digit level; (b) all operands and results are communicated digit serially, and (c) result digits are on-line obtained after a few initial delay. On the other hand, among some of its disadvantages are: (a) it requires more complex three-input signed-digit addition operation; (b) it needs more complicated quotient decision circuit for range detection of the remainder, and (c) output results have to be converted to binary representations.